1. Field of the Invention
The present invention relates to techniques for providing network security. More specifically, the present invention relates to a method and an apparatus that uses a password-derived prime number to facilitate a secure key exchange between devices on a network.
2. Related Art
The advent of computer networks has led to an explosion in the development of applications, such as client-server applications, which operate by transferring information between computational devices across computer networks.
One problem with sending information across computer networks is that it is hard to ensure that sensitive information is kept confidential. This is because a message containing sensitive information can potentially traverse many different computer networks and many different computer systems before it arrives at its ultimate destination. An adversary can potentially intercept a message at any of these intermediate points along the way.
One way to remedy this problem is to establish a “secure communication session” between computer systems. A secure communication session typically uses one or more shared secret keys to encrypt and decrypt information that is transferred between the computer systems.
One commonly used technique for establishing a secure communication session involves an anonymous Diffie-Hellman exchange. A Diffie-Hellman exchange allows two computer systems to agree on a secret shared key by exchanging messages across an insecure network. Referring the FIG. 1, a Diffie-Hellman exchange begins by allowing two parties, such as a client 100 and a server 101, to pick random numbers x and y, respectively (steps 102 and 104). Client 100 then computes X=gx mod P, where P is a large prime number and g is number less than P with certain restrictions that are not important for a basic understanding of the method (step 106). (Note that both g and P can be publicly known.) Similarly, server 101 computes Y=gy mod P (step 108). Next, client 100 and server 101 exchange X and Y (steps 110 and 112). Client 100 then computes the shared secret key as Ks=Yx mod P (step 114). Server 101 similarly computes the shared secret key as Ks=Xy mod P (step 116). Note that Xy mod P=(gx)y=gxy=(gy)x=Yx mod P, which means that client 100 and server 101 have produced the same shared secret key, Ks. Furthermore, note that it is computationally infeasible for an adversary to calculate the shared secret key Ks even if the adversary knows the values of g, P, X, and Y. Consequently, an adversary who observes the communications between client 100 and server 101 is unable to obtain the shared secret key Ks. Next, client 100 and server 101 are able to use this shared secret key Ks to encrypt subsequent communications with each other.
A major weakness with Diffie-Hellman is that there is no authentication, which means that a computer system can unknowingly establish a secret key with an adversary. This situation can be prevented by establishing passwords between the client and server for authentication purposes. For example, the client can present its password to the server, and in response, the server can present a corresponding password to the client.
Unfortunately, the above solution to the authentication problem is vulnerable to a man-in-the-middle attack, in which an adversary sits between the client and the server on the network. To the client the adversary poses as the server, and to the server the adversary poses as the client. In this way, the adversary can authenticate itself as the client to the server by forwarding the password it received from the client to the server. The adversary can also authenticate itself as the server to the client by forwarding the corresponding password it received from the server to the client.
Hence, what is needed is a method and an apparatus that performs a secure key exchange without being vulnerable to a man-in-the-middle attack.